Search Results

Documents authored by Zhou, Neng-Fa

Document
DOI: 10.4230/LIPIcs.SAT.2023.30
A Comparison of SAT Encodings for Acyclicity of Directed Graphs

Authors: Neng-Fa Zhou, Ruiwei Wang, and Roland H. C. Yap

Published in: LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)

Abstract
Many practical applications require synthesizing directed graphs that satisfy the acyclic constraint along with some side constraints. Several methods have been devised for encoding acyclicity of directed graphs into SAT, each of which is based on a cycle-detecting algorithm. The leaf-elimination encoding (LEE) repeatedly eliminates leaves from the graph, and judges the graph to be acyclic if the graph becomes empty at a certain time. The vertex-elimination encoding (VEE) exploits the property that the cyclicity of the resulting graph produced by the vertex-elimination operation entails the cyclicity of the original graph. While VEE is significantly smaller than the transitive-closure encoding for sparse graphs, it generates prohibitively large encodings for large dense graphs. This paper reports on a comparison study of four SAT encodings for acyclicity of directed graphs, namely, LEE using unary encoding for time variables (LEE-u), LEE using binary encoding for time variables (LEE-b), VEE, and a hybrid encoding which combines LEE-b and VEE. The results show that the hybrid encoding significantly outperforms the others.
Cite as

Neng-Fa Zhou, Ruiwei Wang, and Roland H. C. Yap. A Comparison of SAT Encodings for Acyclicity of Directed Graphs. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 30:1-30:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.SAT.2023.30,
  author =	{Zhou, Neng-Fa and Wang, Ruiwei and Yap, Roland H. C.},
  title =	{{A Comparison of SAT Encodings for Acyclicity of Directed Graphs}},
  booktitle =	{26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)},
  pages =	{30:1--30:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-286-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{271},
  editor =	{Mahajan, Meena and Slivovsky, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.30},
  URN =		{urn:nbn:de:0030-drops-184927},
  doi =		{10.4230/LIPIcs.SAT.2023.30},
  annote =	{Keywords: Graph constraints, Acyclic constraint, SAT encoding, Graph Synthesis}
}
Document
DOI: 10.4230/OASIcs.ICLP.2017.11
Efficient Declarative Solutions in Picat for Optimal Multi-Agent Pathfinding

Authors: Neng-Fa Zhou and Roman Bartak

Published in: OASIcs, Volume 58, Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)

Abstract
The multi-agent pathfinding (MAPF) problem has attracted considerable attention because of its relation to practical applications. The majority of solutions for MAPF are algorithmic. Recently, declarative solutions that reduce MAPF to encodings for off-the-shelf solvers have achieved remarkable success. We present a constraint-based declarative model for MAPF, together with its implementation in Picat, which uses SAT and MIP. We consider both the makespan and the sum-of-costs objectives, and propose a preprocessing technique for improving the performance of the model. Experimental results show that the implementation using SAT is highly competitive. We also analyze the high performance of the SAT solution by relating it to the SAT encoding algorithms that are used in the Picat compiler.
Cite as

Neng-Fa Zhou and Roman Bartak. Efficient Declarative Solutions in Picat for Optimal Multi-Agent Pathfinding. In Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017). Open Access Series in Informatics (OASIcs), Volume 58, pp. 11:1-11:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:OASIcs.ICLP.2017.11,
  author =	{Zhou, Neng-Fa and Bartak, Roman},
  title =	{{Efficient Declarative Solutions in Picat for Optimal Multi-Agent Pathfinding}},
  booktitle =	{Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)},
  pages =	{11:1--11:2},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-058-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{58},
  editor =	{Rocha, Ricardo and Son, Tran Cao and Mears, Christopher and Saeedloei, Neda},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2017.11},
  URN =		{urn:nbn:de:0030-drops-84595},
  doi =		{10.4230/OASIcs.ICLP.2017.11},
  annote =	{Keywords: Multi-agent Path Finding, SAT, MIP, Picat}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.SLATE.2013.5
Picat: A Scalable Logic-based Language and System (Invited Talk)

Authors: Neng-Fa Zhou

Published in: OASIcs, Volume 29, 2nd Symposium on Languages, Applications and Technologies (2013)

Abstract
This talk will give the design principles of the Picat language (http://www.picat-lang.org), highlight the high-level and intuitive abstractions provided by Picat for easy programming, and contemplate why Picat is more robust and scalable than Prolog and could be more accessible than Prolog to ordinary programmers for scripting and modeling tasks.
Cite as

Neng-Fa Zhou. Picat: A Scalable Logic-based Language and System (Invited Talk). In 2nd Symposium on Languages, Applications and Technologies. Open Access Series in Informatics (OASIcs), Volume 29, pp. 5-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{zhou:OASIcs.SLATE.2013.5,
  author =	{Zhou, Neng-Fa},
  title =	{{Picat: A Scalable Logic-based Language and System}},
  booktitle =	{2nd Symposium on Languages, Applications and Technologies},
  pages =	{5--6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-52-1},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{29},
  editor =	{Leal, Jos\'{e} Paulo and Rocha, Ricardo and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2013.5},
  URN =		{urn:nbn:de:0030-drops-40273},
  doi =		{10.4230/OASIcs.SLATE.2013.5},
  annote =	{Keywords: Functions, Relations, Loops, Constraints, Tabling}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact